class Solution {
public:
    int longestValidParentheses(string s) {
        // ( ( ) ) ) ( ( ( ( ) ) )
        // 用栈解决，这个栈存储的是下标

        /*
           比如"(())"，遇到'('就push，遇到')'就pop，然后当前i的值与top()的值相减就是结果
           先push(0)，再push(1)，然后遇到')'，此时i是2，先pop()，再i-top()就是2-0=2
        */

        // 1. 先push(-1)
        // 为什么要先push(-1)，举个例子，如果是"())"这个例子
        // 先push(0)，此时栈顶就是'('，此时来了一个')'，那么就pop()
        // 此时i是1，栈里已经已经没有数据了，但是此时我们是可以返回结果的，这个结果应该是2，那i要减多少才是2呢?
        // 很明显，应该是-1，所以我们最开始就要把-1push进去

        // 2. 遇到'('就push
        
        // 3. 遇到')'就pop，
        // 1). 栈不为空时，当前i的值与top()的值相减
        // 2). 栈为空时，把当前')'所对应的下标ipush进去，栈为空，然后又遇到')'，就说明不连续了，有分割了

        stack<int> st;
        st.push(-1);
        int ans = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '(') st.push(i);
            else
            {
                st.pop();
                if(st.empty()) st.push(i);
                else ans = max(ans, i - st.top());
            }
        }
        return ans;
    }
};